import heapq


def dijkstra(nodes, matrix):
    n = len(matrix)
    dist = [[float('inf')] * n for _ in range(n)]
    path = [[-1] * n for _ in range(n)]

    for node in nodes:
        dist[node][node] = 0.0
        queue = [(0.0, node)]
        while queue:
            _, u = heapq.heappop(queue)
            for v in range(n):
                if matrix[u][v] != float('inf') and dist[node][u] + matrix[u][v] < dist[node][v]:
                    dist[node][v] = dist[node][u] + matrix[u][v]
                    path[node][v] = u
                    heapq.heappush(queue, (dist[node][v], v))

    result = {}
    for u in nodes:
        for v in nodes:
            if u != v:
                result[(u, v)] = (dist[u][v], [])
                if dist[u][v] != float('inf'):
                    cur = v
                    while cur != u:
                        result[(u, v)][1].append(cur)
                        cur = path[u][cur]
                    result[(u, v)][1].append(int(u))
                    result[(u, v)][1].reverse()
    return result

# 邻接矩阵表示图中的边和权重
matrix = [
    [0, 10, float('inf'), 5, float('inf')],
    [float('inf'), 0, 1, 2, float('inf')],
    [float('inf'), float('inf'), 0, float('inf'), 4],
    [float('inf'), 3, 9, 0, 2],
    [7, float('inf'), 6, float('inf'), 0]
]


# # 我们关注的节点
# nodes = [0, 1, 3]
#
# # 使用 Dijkstra 算法计算最短路径和距离
# result = dijkstra(nodes, matrix)
#
# # 打印结果
# print(result)
# for key, value in result.items():
#     print(f"从节点 {key[0]} 到节点 {key[1]} 的最短距离为：{value[0]}，最短路径为：{value[1]}")